Perfect codes in Cayley graphs

Abstract

Given a graph Γ, a subset C of V (Γ) is called a perfect code in Γ if every vertex of Γ is at distance no more than one to exactly one vertex in C, and a subset C of V (Γ) is called a total perfect code in Γ if every vertex of Γ is adjacent to exactly one vertex in C. In this paper we study perfect codes and total perfect codes in Cayley graphs, with a focus on the following themes: when a subgroup of a given group is a (total) perfect code in a Cayley graph of the group; and how to construct new (total) perfect codes in a Cayley graph from known ones using automorphisms of the underlying group. We prove several results around these questions.